package compress.lzw;

import java.io.UnsupportedEncodingException;
import java.nio.charset.Charset;
import java.util.*;

public class LZW {
    /**
     * Compress a string to a list of output symbols.
     */
    public static List<Integer> compress(String uncompressed) {
        // Build the dictionary.
        int dictSize = 128;
        Map<String, Integer> dictionary = new HashMap<String, Integer>();
        for (int i = 0; i < dictSize; i++)
            dictionary.put("" + (char) i, i);

        String w = "";
        List<Integer> result = new ArrayList<Integer>();
        for (char c : uncompressed.toCharArray()) {
            String wc = w + c;
            if (dictionary.containsKey(wc))
                w = wc;
            else {
                result.add(dictionary.get(w));
                // Add wc to the dictionary.
                dictionary.put(wc, dictSize++);
                w = "" + c;
            }
        }

        // Output the code for w.
        if (!w.equals(""))
            result.add(dictionary.get(w));
        return result;
    }

    /**
     * Decompress a list of output ks to a string.
     */
    public static String decompress(List<Integer> compressed) {
        // Build the dictionary.
        int dictSize = 128;
        Map<Integer, String> dictionary = new HashMap<Integer, String>();
        for (int i = 0; i < 128; i++)
            dictionary.put(i, "" + (char) i);

        String w = "" + (char) (int) compressed.remove(0);
        StringBuffer result = new StringBuffer(w);
        for (int k : compressed) {
            String entry;
            if (dictionary.containsKey(k))
                entry = dictionary.get(k);
            else if (k == dictSize)
                entry = w + w.charAt(0);
            else
                throw new IllegalArgumentException("Bad compressed k: " + k);

            result.append(entry);

            // Add w+entry[0] to the dictionary.
            dictionary.put(dictSize++, w + entry.charAt(0));

            w = entry;
        }
        return result.toString();
    }

    public static byte[] toByteArray(List<Integer> s) {
        byte[] b = new byte[s.size()];
        for (int i = 0; i < s.size(); i++) {
            b[i] = s.get(i).byteValue();
        }
        return b;
    }
    public static byte toUnsignedInt(Integer s) {

        return Byte.valueOf(s+"");
    }

    public static void main(String[] args) throws UnsupportedEncodingException {

        String uncompressed = "{\"oid\":\"5c51184906714d0000f7772e\",\"long\":\"100\",\"int\":256,\"date\":\"2019-01-30T03:21:45.287Z\",\"string\":\"js-bson sample\",\"array\":[0,1,1,3,1,1,3,0,0,0,0,0,0,0,0,0,0,0,0],\"array1\":[{\"x\":1,\"y\":1},{\"x\":1,\"y\":1},{\"x\":1,\"y\":1},{\"x\":1,\"y\":1},{\"x\":1,\"y\":1},{\"x\":1,\"y\":1},{\"x\":1,\"y\":1},{\"x\":1,\"y\":1},{\"x\":1,\"y\":1}],\"obj\":{\"string\":\"Object within an object\"}}";
        System.out.println(uncompressed.getBytes("ASCII").length);

        System.out.println("input: " + uncompressed);
        System.out.println("input.byte.len: " + uncompressed.getBytes().length);
        System.out.println("input.len: " + uncompressed.length());
        List<Integer> compressed = compress(uncompressed);
        System.out.println("out: " + compressed);
        System.out.println("out.byte.len: " + toByteArray(compressed).length);
        System.out.println("out.len: " + compressed.size());

        String decompressed = decompress(compressed);
        System.out.println("out.input: " + decompressed);


        System.out.println(decompressed.equals(uncompressed));

        String x = "34,111,105,100,34,58,34,53,99,53,49,49,56,52,57,48,54,55,49,52,100,48,278,48,102,55,282,50,101,34,44,34,108,111,110,103,261,34,49,278,286,34,105,110,116,261,50,53,54,287,100,97,116,285,262,50,48,49,57,45,313,45,51,48,84,48,51,58,50,49,58,52,53,46,50,56,55,90,297,115,116,114,299,292,262,106,115,45,98,115,290,32,115,97,109,112,108,285,287,97,114,114,97,121,261,91,48,44,49,364,44,51,366,365,368,363,372,44,373,375,374,377,372,93,355,357,359,49,361,256,120,261,365,34,360,58,49,125,44,386,388,287,391,393,395,34,387,392,398,388,394,396,404,390,406,401,403,389,399,407,402,397,410,392,416,413,405,420,412,418,415,425,409,415,380,257,98,106,261,256,336,338,291,293,79,433,101,99,116,32,119,105,116,104,299,32,97,110,32,111,442,444,34,125,125";
       System.out.println(x.length());
    }

}